Adaptive filters are used in many applications where it is desired to isolate one signal from another or to remove noise from a desired signal in order to process it and extract information. For instance, in telecommunications or data processing systems it is necessary to sample an incoming signal in order to decode the signal and obtain information from it. This sampling must be carried out at the proper frequency to extract the information from the signal in an optimal manner. This requires accurate control of the sampling process so that it can be modified as needed in accordance with the characteristics of the incoming signal. A standard means of controlling the sampling process is through the use of an adaptive filter.
In such an application, an adaptive filter operates on an incoming signal at time n, x(n), to produce an output at time n, y(n), where the input and output are related by the impulse characteristics of the filter. These filter characteristics are described by a set (or vector) of adaptive filter coefficients, H(n), having components h.sub.i (n), with the filter, the input, and the output being related by: EQU y(n)=X(n).sup.T H(n), (1)
where X(n).sup.T is the transpose of the vector X(n) having components x(n) , EQU X(n).sup.T =[x(n), x(n-1), . . . x(n-m+1)], and H(n).sup.T =[h.sub.0 (n), h.sub.1 (n), . . . h.sub.m-1 (n)]. (2)
Equation (1) describes an output which is the dot product of the two vectors X(n) and H(n), where in this situation the dot product represents the convolution of the input signal and the adaptive filter coefficients: ##EQU1## where m is the number of coefficients in the adaptive filter.
As indicated by equation (2), an adaptive filter can be described by a sequence of m filter coefficients, where the coefficients may be a function of time. The typical problem encountered is one of updating the filter coefficients in a manner which leads to a convergence between the result of applying the adaptive filter to an input signal and the output of a channel through which the signal has propagated. If the channel is characterized by its impulse response as a function of time, H(n), where EQU H(n).sup.T =[h.sub.0 (n), h.sub.1 (n), . . . h.sub.m-1 (n)],(3)
then the result of propagating a signal X(n) through the channel is given by the channel output, Y(n), where the components y(n) of Y(n) arc given by the dot product (convolution) of X(n) and H(n): EQU y(n)=X(n).sup.T H(n). (4)
If the difference between the channel output and the adaptive filter output is defined to be an error term, e(n), where EQU e(n)=y(n)-y(n), (5)
then the problem can be expressed as one of iteratively updating the adaptive filter coefficients so as to minimize e(n). The expression describing the minimal value of e(n) can take several forms, depending upon the metric selected to represent a minimum, e.g., the absolute value of e(n), the mean square value of e(n), etc.
The general situation is depicted in FIG. 1, which shows a signal X(n) being input to an adaptive filter 10 and a channel 12, with the outputs of filter 10 and channel 12 being differenced by a comparator 14, thereby producing an error term e(n). In the usual case, e(n) is then fed back to filter 10 to cause an updating of the filter coefficients. This iterative process is continued until the filter coefficients have converged to a sufficient approximation of the channel response, i.e., .vertline.f{e(n)}.vertline. is small, where f{e(n)} is some function of e(n) which is being minimized.
Adaptive filters can also be used to perform noise cancellation. In this use of adaptive filters, an input signal representing a desired signal which is corrupted by additive noise is compared with a reference signal. The reference signal is selected so that it represents a good estimate of the noise source with minimal contribution from the desired signal. The reference signal is filtered and subtracted from the combined signal and additive noise to form an output signal. If the desired signal is s, the additive noise is n.sub.o, the reference signal is n.sub.1, and the filtered reference signal is y, then the output signal z is given by: EQU z=s+n.sub.o -y, (6)
where y results from the operation of an adaptive filter on n.sub.1.
If y is adjusted to be a sufficiently "good" estimate of the noise term n.sub.o, then the output signal (z) will become a better estimate of the desired signal (s). This is accomplished by feeding the output signal back into an adaptive filter as an error signal and iteratively updating the adaptive filter coefficients until an acceptable result is obtained. In this application of an adaptive filter, the desired set of filter coefficients is one which causes the filtered reference noise signal to approach the actual noise added to the desired signal. When this occurs, the additive noise term is effectively "cancelled" and the actual desired signal is obtained.
Updating the coefficients of an adaptive filter is usually carried out by a method which iteratively updates each coefficient as the time increments from time (n) to time (n+1). A general form of an update equation is given by: EQU H(n+1)=H(n)+g(n) f.sub.1 (e(n)) f.sub.2 (X(n)), (7)
where g(n) is a gain term and f.sub.1 and f.sub.2 are generalized functions of the indicated variables.
A well-known adaptation equation having the form shown in equation (7) is the Least Mean Squares (LMS) algorithm which is intended to adjust the coefficients of an adaptive filter so as to minimize the mean-square error. Since the mean-square error is a quadratic function of the weights, adjusting the coefficients to minimize the mean-square error can be visualized as attempting to reach the bottom of a hyper-paraboloidal surface by descending along its sides. As is well known, gradient methods are typically used to accomplish this goal. The LMS algorithm is an implementation of one of these gradient methods known as the method of steepest descent, and in terms of the components h.sub.j (n) of the vector H(n) is described by: EQU h.sub.j (n+1)=h.sub.j (n)+2 .mu.e(n)x(n-j), (8)
where .mu. is the adaptation step size which controls the rate of convergence. Equation (8) can be expressed in vector form as: EQU H(n+1)=H(n)+2 .mu.e(n)X(n).
The e(n)x(n-j) term in equation (8) represents an error-signal correlator. As will be discussed later, other types of correlators, such as sign-sign, sign-error, and sign-signal have also been used to update the filter coefficients in adaptive echo cancelers and equalizers.
FIG. 2 is a block diagram of a device for implementing an adaptive filtering scheme based on the LMS algorithm. In FIG. 2, an input signal 100 represented by X.sub.j has components X.sub.ij, where (i=1, . . . ,n). Each X.sub.ij component is fed to a multiplier 110 as well as to adaptive filter 120. The multipliers 110 act to weight the input signal components by weighting terms W.sub.ij to produce a set of product terms, X.sub.ij W.sub.ij. These weighted terms are summed by integrator 130 and provided to both the filter output and to a comparator 140.
A desired response signal 142 is also input to comparator 140, which differences the filter output and desired response to obtain an error signal. The error signal is fed back to adaptive filter 120 which then implements a desired update algorithm to update the filter coefficients. The updated filter coefficients then become the new weighting terms used by integrators 130. This iterative process is continued until the filter coefficients converge to an acceptable value. Note that in some applications, such as the use of the LMS algorithm, all of the X.sub.ij inputs may be derived from a signal which is put through a delay line, so that each input term is a sample of the same signal corresponding to a different time.
In addition to the LMS algorithm, other update equations have also been investigated. A more general expression for an update equation for the coefficients of an adaptive filter is described by: EQU h.sub.j (n+1)=h.sub.j (n)-2 .mu.Q([e(n)x(n-j)], (9)
where Q[ ] is a generalized function of e(n)x(n-j) and .mu. is again the adaptation step size, the value of which can be selected to assure convergence. Equation (9) describes how a particular filter coefficient is updated from time (n) to time (n+1). In using an update equation, the error term given in equation (5) is often modified to include a term, u(n), which represents additive gaussian noise. In this case, equation (5) takes the form: EQU e(n)=y(n)-y(n)+u(n). (5a)
The generalized function Q[ ] may be non-linear and can take many forms, examples of which are given below: EQU Q.sub.1 [e(n)x(n-j)]=e(n)x(n-j) (10) EQU Q.sub.2 [e(n)x(n-j)]=sgn[e(n)]x(n-j) (11) EQU Q.sub.3 [e(n)x(n-j)]=e(n)sgn[x(n-j)] (12) EQU Q.sub.4 [e(n)x(n-j)]=sign[e(n)]sgn[x(n-j)] (13)
where sgn[z]=1 if z.gtoreq.1, and sgn[z]=-1 if z&lt;1. Equation (13) is known as the Polarity Coincidence Correlator (PCC).
Compared to other update algorithms, the LMS update algorithm has the advantage that if it were implemented with infinite bit precision, it would have the fastest convergence of the commonly used update functions. However, in actual situations when it is implemented with finite bit precision, it may not be not as well-behaved as desired. In a digital implementation of the LMS algorithm, when convergence starts, e(n) is large and .mu. is typically fixed at .mu.=1/(2.sup.11). The coefficients H(n) are 24 bits wide (1 sign bit+23 magnitude bits). The product p=.mu.e(n) is equivalent to shifting e(n) to the right by 11 places and, initially, when e(n) is large, p is still on average such that .linevert split.p.linevert split.&gt;1/(2.sup.23) and, therefore, this update is "seen" by H(n). However, as convergence progresses and e(n) becomes smaller as desired, .linevert split.p.linevert split.&lt;1/(2.sup.23) and the coefficients H(n) are not being updated anymore. Therefore, convergence is not optimal, since by using more than 24 bits for H(n), convergence could have continued and e(n) could have been decreased further.
The LMS algorithm has also shown parameter drift properties that are described by Sethares et al. in "Parameter Drift in LMS Adaptive Filters", IEEE Transactions on Acoustics, Speech and Signal Processing, Vol. ASSP-34 No. 4, August 1986, and which have been observed in a working prototype. The problem is that, with bounded steady state inputs, the output x(n) and the error e(n) remain bounded and approximately zero, respectively, while the parameters H(n) drift away from H very slowly.
Another disadvantage of using LMS algorithms is that their hardware implementations require some degree of complexity. Since LMS algorithms require that the product of e(n)X(n) be determined, multipliers are needed to carry out the calculation. This is in contrast to sign-based update equation implementations which are simpler because sgn(e) or sgn(x) equals plus or minus one.
Although update algorithms other than the LMS algorithm have been studied and used in adaptive filtering applications, the literature has noted that they also have disadvantages. It has been observed that convergence time, steady state residual error, or both are sacrificed in most implementations of sign correlators. The primary reason for these behaviors of sign algorithms is that e(n) or x(n) are approximated by their sign instead of their actual values. This slows down the convergence of the filter coefficients since the actual value is rarely equal to plus or minus one. Therefore, both families of correlators typically used in update equations incorporate non-optimal performance features.
In many applications which use adaptive filters, the quantity of interest is the power spectrum of a signal. The power spectrum is defined to be the fourier transform of the autocorrelation of a signal, that is the correlation of a signal with itself. If the propagation of a signal through a channel is viewed as a transformation operating on that signal, it is apparent that it is of some interest how the autocorrelation sequences (the autocorrelation coefficients of a signal for different times) of an input signal and a transformed signal are related. This problem has been solved and is expressed in terms of Price's Theorem, which states that given a stationary Gaussian zero mean continuous time series, f(t), undergoing a memoryless non-linear transformation, F[f(t)], to produce an output, g(t), then if the autocorrelation sequence for f(t) is .rho..sub.f (.tau.), with .tau. being the correlation delay, the autocorrelation sequence for the output, .rho..sub.g (.tau.), is related to .rho..sub.f (.tau.) by: ##EQU2## where F.sup.k denotes k derivatives with respect to f and the bar over the right hand side of equation (14) denotes the expected value.
For the sgn[z] function described above, i.e., F[f(t)]=sgn[f(t)], Price's Theorem indicates that the input and output correlation sequences are related according to: EQU .rho..sub.f (.tau.)=sin (.pi./2 .rho..sub.g (.tau.)). (15)
If the continuous variable .tau. is replaced with a sequence of n time samples, the result given in equation (14) still holds and: EQU .rho..sub.f (n)=sin (.pi./2 .rho..sub.g (n)). (16)
Equation (16) can be inverted to yield: EQU .rho..sub.g (n)=2/.pi. arc sin (.rho..sub.f (n). (17)
Using equation (9), the Polarity Coincidence Correlator coefficient update relationship given in equation (13) can be rewritten in vector form as ##EQU3## where E{ } represents the expected value of the indicated terms. Equation (18) clearly shows that a sgn[z] discontinuity produces a coefficient update equation which includes a distortion factor of the form (2/.pi. arcsin [ ]). This means that an adaptive filter having coefficients modified according to a PCC iterative process will converge in an oscillating manner instead of approaching the final value(s) directly. This can present problems in some applications because the convergence will be slower than may be desired.
What is desired is a method of updating the coefficients of an adaptive filter which overcomes the disadvantages of the LMS or PCC type algorithms typically used, and an apparatus embodying the method.